package leetcode.list;

import java.util.HashSet;

/**
 * Created by zxc on 2018/10/2.
 * 两个链表的交点，时间复杂度O（n），空间复杂度O（1）
 */
public class IntersectionTwoList {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    /*两个链表的交点 使用HashSet来做*/
    private static ListNode findIntersectionTwoListA(ListNode headA, ListNode headB) {
        ListNode retNode = null;
        HashSet<ListNode> lst = new HashSet<>();
        while (headA != null){
            lst.add(headA);
            headA = headA.next;
        }
        while (headB != null){
            if(lst.contains(headB)){
                retNode = headB;
                break;
            }
            headB = headB.next;
        }
        return retNode;
    }

    /*两个链表的交点，时间复杂度O（n），空间复杂度O（1） */
    private static ListNode findIntersectionTwoListB(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        int lenAB = 0;
        ListNode headATemp = headA;
        ListNode headBTemp = headB;
        // 计算A链表长度
        while (headATemp != null){
            ++lenA;
            headATemp = headATemp.next;
        }
        // 计算B链表长度
        while (headBTemp != null){
            ++lenB;
            headBTemp = headBTemp.next;
        }
        if(lenA > lenB){
            lenAB = lenA - lenB;
            while (headA != null && (lenAB--)!=0){
                headA = headA.next;
            }
        }else{
            lenAB = lenB - lenA;
            while (headB != null && (lenAB--)!=0){
                headB = headB.next;
            }
        }
        while(headA != null && headB != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);

        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);

        node1.next=node2;
        node2.next=node3;
        node3.next=node6;

        node4.next=node5;
        node5.next=node6;

        node6.next=node7;
        node7.next=null;
        ListNode  headA = node1;
        ListNode  headB = node4;

        System.out.println("Before find:");
        System.out.print("headA:");
        while (headA!=null){
            System.out.print(headA.val+">");
            headA = headA.next;
        }
        System.out.println("end");
        System.out.print("headB:");
        while (headB!=null){
            System.out.print(headB.val+">");
            headB = headB.next;
        }
        System.out.println("end");

        /*简单的链表逆序*/
        ListNode newHead = findIntersectionTwoListB(node1, node4);

        if(newHead != null) {
            System.out.println("find交点：" + newHead.val);
        }else{
            System.out.println("无交点" );
        }

        System.out.println("end");
    }
}
